import java.util.HashMap;
import java.util.Map;


public class FibbonaciNumbers {

	public static void main(String[] args) {
		
		System.out.println(fib(6));
		
		System.out.println(fib(9));
		
		System.out.println(fib(10));
		
		System.out.println(fib(11));
		
		System.out.println(fib2(1));
		
		System.out.println(fib2(0));
		
		System.out.println(fib2(6));
		
		Map<Integer, String> m = new HashMap<Integer, String>();
		
		m.containsKey(9);
		
		for(Map.Entry<Integer, String> entry : m.entrySet()) {
			Integer i = entry.getKey();
			String value = entry.getValue();
		}
		
	}

	private static int fib(int nr) {
		
		if (nr == 1 || nr == 2) {
			return 1;
		} else {
			return fib(nr-1) + fib(nr-2);
		}
		
	}
	
	private static int fib2(int n) {
		
		if (n == 0 || n== 1) {
			return n == 1 ? 1 : 0;
		}
		
		int i = n-1;
		int a = 1;
		int b = 0;
		while (i-- > 0) {
			int tmp = a;
			a = a + b;
			b = tmp;
		}
		return a;
	}
}
